from leetcode_test import TreeNode

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        """和根节点比较，如果大于根节点，就放在右边，不然就放在左边
        4
       / \
      2   7
     / \
    1   3
    这种如果插入的是6，就需要
    new_node.right = root.right
    root.right = new_node
        """

        if not root:
            return TreeNode(val)
        if val > root.val:
            if root.right:
                self.insertIntoBST(root.right, val)
            else:
                root.right = TreeNode(val)
        else:
            if root.left:
                self.insertIntoBST(root.left, val)
            else:
                root.left = TreeNode(val)
        return root

def test1():
    root = TreeNode.create([4,2,7,1,3])
    res = Solution().insertIntoBST(root, 5)
    assert res.get_value() == [4,2,7,1,3,5]

def test2():
    root = TreeNode.create([])
    res = Solution().insertIntoBST(root, 3)
    assert res.get_value() == [3]
# test1()